package 删除字符串中的所有相邻重复项;

import java.util.Stack;

public class Solution {
    /*
    给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
    在 s 上反复执行重复项删除操作，直到无法继续删除。
    在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
     */
    public String removeDuplicates(String s) {
        // 通过栈的思想
        // 为什么想到栈呢？
        // 因为栈顶有个特性，始终保存了我们需要比较的相邻字符1，我们只需要将相邻字符2与之进行比较即可(倘若删除了栈顶元素，那么又会暴露出新的相邻字符1,避免了使用指针的麻烦操作)

        Stack<Character> stack = new Stack<>();
        if (s.isEmpty())
            return s;
        // 将第一个元素入栈，启动循环
        stack.push(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            if (stack.isEmpty() || c != stack.peek()) {
                // 不相同或者栈当前为空，则将元素入栈
                stack.push(c);
            } else {
                // 如果相同，则从栈中删除该元素。
                stack.pop();
            }
        }
        // 将栈中元素转换为字符串
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.insert(0,stack.pop());
        }
        return sb.toString();
    }
}